//给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。 
//
// 
//
// 示例 1： 
//
// 
//输入：mat = [[1,2,3],[4,5,6],[7,8,9]]
//输出：[1,2,4,7,5,3,6,8,9]
// 
//
// 示例 2： 
//
// 
//输入：mat = [[1,2],[3,4]]
//输出：[1,2,3,4]
// 
//
// 
//
// 提示： 
//
// 
// m == mat.length 
// n == mat[i].length 
// 1 <= m, n <= 10⁴ 
// 1 <= m * n <= 10⁴ 
// -10⁵ <= mat[i][j] <= 10⁵ 
// 
// Related Topics 数组 矩阵 模拟 👍 243 👎 0


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] findDiagonalOrder(int[][] matrix) {
        if(matrix == null || matrix.length == 0){
            return new int[0];
        }
        //矩阵行数
        int row = matrix.length;
        //矩阵列数
        int col = matrix[0].length;
        //res数组下标
        int k = 0;
        int[] res = new int[row * col];
        List<Integer> temp = new ArrayList<>();

        for (int i = 0; i < row + col - 1; i++){
            temp.clear();
            //每次存储从右上到左下的对角线元素，这样的对角线总共有m + n - 1条，起点为第一行或者最后一列的元素。
            //如果是偶数条，则将元素翻转，再放入res。
            int r = i < col ? 0 : i - col + 1;
            int c = i < col ? i : col - 1;
            while (r < row && c > -1){
                temp.add(matrix[r][c]);
                r++;
                c--;
            }

            if(i % 2 ==0){
                Collections.reverse(temp);
            }

            for (int j = 0; j < temp.size(); j++){
                res[k++] = temp.get(j);
            }
        }
        return res;
    }
}

//leetcode submit region end(Prohibit modification and deletion)
